Implement Queue using Stacks
Leetcode #232 | Easy | Очередь | Стек | Design
Идея
Два стека, один принимает все элементы. При обращении (push или peek) переносим все во второй стек, по свойствам стека во время переноса первый элемент окажется первым на выход - FIFO, что нам и надо
Big-O
- Время
O(1) - Память
O(N)
Код
class MyQueue {
private Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
public void push(int x) { in.push(x); }
public int pop() { relocate(); return out.pop(); }
public int peek() { relocate(); return out.peek(); }
public boolean empty() { return in.isEmpty() && out.isEmpty(); }
private void relocate() {
if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
}
}